package com.hardy.DynamicProgramm;

/**01背包问题
 * Created by 1340760685@qq.com on 2016/9/24.
 */
public class Backpack01Problem {
    //背包载重m千克，物品个数n,每个物品的质量数组w,每个物品的价值v
    public static int[][] slove(int m,int n,int[] w,int[] v){
        //c[i][j] 背包中放置0...i个物品质量为j时的价值
        int[][] c=new int[n+1][m+1];
        for(int i=0;i<n+1;i++){
            c[i][0]=0;//背包中放置0....i个物品，总质量为0的总价值为0;
        }
        for(int j=0;j<m+1;j++){
            c[0][j]=0;//背包中不放物品，总质量为j时，总价值为0;
        }
        for(int i=1;i<n+1;i++){
            for(int j=1;j<m+1;j++){
                //如果第i-1个物品质量已经大于j了，那么第i个物品不能放入故c[i][j]=c[i-1][j]
                //否则第i个物品既可以放入也可不放入，两者求最大值
                //如果第i个物品放入，那么背包还剩下个空间为j-w[i-1],价值要加上v[i+1];
                if(w[i-1]<=j){
                    c[i][j]=Math.max(c[i-1][j],c[i-1][j-w[i-1]]+v[i-1]);
                }else{
                    c[i][j]=c[i-1][j];
                }
            }
        }
        return c;
    }

    public static int[] printPack(int m,int n,int[][] c,int[] w){
        int[] x=new int[n];
        //如果c[i][m]大于c[i-1][m]，说明c[i][m]这个最优值中包含了w[i-1](注意这里是i-1，因为c数组长度是n+1)
        for (int i=n;i>0;i--){
            if(c[i][m]>c[i-1][m]){
                x[i-1]=1;
                m-=w[i-1];
            }
        }
        return x;
    }

    public static void main(String[] args) {
        int m =10;
        int n=3;
        int[] w={3,4,5};
        int[] v={4,5,6};
        int[][] c=slove(m,n,w,v);
        int[] result=printPack(m,n,c,w);
        for(int i=0;i<result.length;i++){
            System.out.print(result[i]+" ");
        }
    }
}
